package com.ljy.my_study.leetcode.K个不同整数的子数组;

import java.time.Duration;
import java.time.Instant;

public class TestMain2 {
//    https://leetcode-cn.com/problems/subarrays-with-k-different-integers/solution/k-ge-bu-tong-zheng-shu-de-zi-shu-zu-by-l-ud34/
//    双指针
    public static void main(String[] args) {
        int[] A=new int[]{1,2,1,3,4};
        int K=3;
        Instant start = Instant.now();
        System.out.println(new TestMain2().subarraysWithKDistinct(A,K));
        A=new int[]{1,2,1,2,3};
        K=2;
        System.out.println(new TestMain2().subarraysWithKDistinct(A,K));
        A=new int[]{1,2,1,3,4};
        K=3;
        System.out.println(new TestMain2().subarraysWithKDistinct(A,K));
        Instant end = Instant.now();
        System.out.println(Duration.between(start,end).toMillis());
    }

    public int subarraysWithKDistinct(int[] A, int K) {
        return atMostKDistinct(A, K) - atMostKDistinct(A, K - 1);
    }

    /**
     * @param A
     * @param K
     * @return 最多包含 K 个不同整数的子区间的个数
     */
    private int atMostKDistinct(int[] A, int K) {
        int len = A.length;
        int[] freq = new int[len + 1];

        int left = 0;
        int right = 0;
        // [left, right) 里不同整数的个数
        int count = 0;
        int res = 0;
        // [left, right) 包含不同整数的个数小于等于 K
        while (right < len) {
            if (freq[A[right]] == 0) {
                count++;
            }
            freq[A[right]]++;
            right++;

            while (count > K) {
                freq[A[left]]--;
                if (freq[A[left]] == 0) {
                    count--;
                }
                left++;
            }
            // [left, right) 区间的长度就是对结果的贡献
            res += right - left;
        }
        return res;
    }
}
